package problem402;

import java.util.Stack;

//402.移掉K位数字
//https://leetcode.cn/problems/remove-k-digits/

class Solution {
    public String removeKdigits(String num, int k) {
        int n = num.length();
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i<n; i++) {
            if(stack.isEmpty() || num.charAt(i) > stack.peek() || k == 0) {
                stack.push(num.charAt(i));
            }else {
                while(!stack.isEmpty() && num.charAt(i) < stack.peek() && k > 0) {
                    stack.pop();
                    k--;
                }
                stack.push(num.charAt(i));
            }
        }

        while(!stack.isEmpty() && k-- > 0) {
            stack.pop();
        }

        StringBuffer ret = new StringBuffer();
        while(!stack.isEmpty()) {
            ret.append(stack.pop());
        }
        while(ret.length() > 0 && ret.charAt(ret.length()-1) == '0') {
            ret.deleteCharAt(ret.length()-1);
        }

        return ret.length() == 0 ? "0" : ret.reverse().toString();
    }
}

/*

4832  3

3234381 3
2331

10200 1

1003243  2
00243

*/